package Algorithm.dynamicProgramming.introduct;

/**
 * 二维打家劫舍
 * 题目简述：从一个2行n列的二维数组中选数，选的任意两个数上下左右都不能相邻，求能抢到的最大价值和
 */
public class Rob2D {

    /**
     * 思路：关于线性dp的题，当前状态一定是依赖于前相邻状态的，要找到线性dp的角度
     *
     * 1. 定义dp：dp[i][0]为在前i列中不抢第i列的最大价值，dp[i][1]为抢第i列的第1个的最大价值，dp[i][2]为抢第i列的第2个的最大价值
     * 2. 状态转移公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
     *               dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + value[0][i]
     *               dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + value[1][i]
     * 3. 初始化：dp[0][1] = value[0][0];dp[0][2] = value[1][0];
     * 4. 遍历方式：从前往后逐列遍历
     */
    public long maxRobValue(int[][] value) {
        int n = value[0].length;
        int[][] dp = new int[n][3];
        dp[0][1] = value[0][0];dp[0][2] = value[1][0];
        for (int i = 1;i < n;i++) {
            dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][2]) + value[0][i];
            dp[i][2] = Math.max(dp[i-1][0], dp[i-1][1]) + value[1][i];
        }
        return Math.max(Math.max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
    }

    public static void main(String[] args) {
        System.out.println(new Rob2D().maxRobValue(new int[][]{
                {1, 1, 100},
                {100, 1, 1}
        }));
        System.out.println(new Rob2D().maxRobValue(new int[][]{
                {1, 2, 3},
                {4, 5, 6}
        }));
    }
}
